package com.atguigui.leetcode;

import java.util.ArrayDeque;
import java.util.HashSet;
import java.util.Queue;
import java.util.Set;

/**
 * 433.最小基因变化
 * Project: leetcode
 * Package: com.atguigui.leetcode
 * Version: 1.0
 * <p>
 * Created by WJX on 2022/5/7 9:08
 */
public class P433MinimumGeneticMutation {
    public static void main(String[] args) {
        Solution solution = new P433MinimumGeneticMutation().new Solution();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int minMutation(String start, String end, String[] bank) {
            Set<String> cnt = new HashSet<String>();
            Set<String> visited = new HashSet<String>();
            char[] keys = {'A', 'C', 'G', 'T'};
            for (String w : bank) {
                cnt.add(w);
            }

            // start和end相等直接返回
            if (start.equals(end)) {
                return 0;
            }
            // 如果end不在 bank中 直接返回 -1
            if (!cnt.contains(end)) {
                return -1;
            }

            Queue<String> queue = new ArrayDeque<String>();
            queue.offer(start);
            visited.add(start);
            int step = 1;

            while (!queue.isEmpty()) {
                int sz = queue.size();
                for (int i = 0; i < sz; i++) {
                    // 检索并删除第一条数据
                    String curr = queue.poll();

                    // 循环遍历8个字符
                    for (int j = 0; j < 8; j++) {

                        //依次在 'A', 'C', 'G', 'T' 中对比
                        for (int k = 0; k < 4; k++) {
                            // 不等于
                            if (keys[k] != curr.charAt(j)) {
                                StringBuffer sb = new StringBuffer(curr);
                                sb.setCharAt(j, keys[k]);
                                String next = sb.toString();
                                //
                                if (!visited.contains(next) && cnt.contains(next)) {
                                    if (next.equals(end)) {
                                        return step;
                                    }
                                    // 加入一次转化
                                    queue.offer(next);
                                    visited.add(next);
                                }
                            }
                        }
                    }
                }
                // 增加次数
                step++;
            }


            return -1;
        }
    }
}
